import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BaseballElimination
{
	private final int       nt_;
	private final int[]     w_;
	private final int[]     l_;
	private final int[]     r_;
	private final int[][]   g_;
	
	private final boolean[] eliminated_;
	private final java.util.LinkedList<String>[] certificates_;
	
	private final java.util.Vector<String> names_ = new java.util.Vector<String>();
	
	// create a baseball division from given filename in format specified below
	public BaseballElimination(String filename)
	{
		try
		{
			final Scanner sc = new Scanner(new File(filename), "UTF-8");
		
			nt_ = sc.nextInt();
			
			eliminated_   = new boolean[nt_];
			certificates_ = new java.util.LinkedList[nt_];
			
			names_.setSize(nt_);
			w_ = new int[nt_];
			l_ = new int[nt_];
			r_ = new int[nt_];
			g_ = new int[nt_][nt_];
			
			for(int i = 0; i < nt_; i++)
			{
				names_.set(i, sc.next());
				w_[i] = sc.nextInt();
				l_[i] = sc.nextInt();
				r_[i] = sc.nextInt();
				
				for(int j = 0; j < nt_; j++)
					g_[i][j] = sc.nextInt();
			}
			
			sc.close();
		}
		catch (FileNotFoundException e)
		{
			throw new java.lang.IllegalArgumentException(e);
		}

		for(int i = 0; i < nt_; i++)
			calculateElimination(i);
	}

	private int getV(int index)
	{
		int V = 2 + nt_;
		
		// now find number of pairs to play
		for(int i = 0; i < nt_; i++)
			for(int j = 0; j < i; j++)
				if(i != index && j != index && g_[i][j] > 0)
					V++;
		
		return V;
	}
	
	private void calculateElimination(int index)
	{
		final int V = getV(index);
		final int s = V - 2;
		final int t = V - 1;

		//StdOut.println("Num edges: " + V);
		
		final int INF_CAPACITY = 9999999;
		
		final FlowNetwork network = new FlowNetwork(V);

		for(int i = 0; i < nt_; i++) {
			int capacity = w_[index] + r_[index] - w_[i];
			if(capacity < 0) {
				eliminated_[index] = true;
				certificates_[index] = new java.util.LinkedList<String>();
				certificates_[index].add(names_.get(i));
				return;
			}
			
			network.addEdge(new FlowEdge(i, t, capacity));
		}
		
		// first nt_ verteces correspond to teams
		int pairEdgeIndex = nt_;
		for(int i = 0; i < nt_; i++)
			for(int j = 0; j < i; j++)
				if(i != index && j != index && g_[i][j] > 0)
				{
//					StdOut.println("Add edge " + s + " " + pairEdgeIndex);
//					StdOut.println("Add edge " + pairEdgeIndex + " " + i);
//					StdOut.println("Add edge " + pairEdgeIndex + " " + j);
					network.addEdge(new FlowEdge( s, pairEdgeIndex, g_[i][j] ));
					network.addEdge(new FlowEdge( pairEdgeIndex, i, INF_CAPACITY ));
					network.addEdge(new FlowEdge( pairEdgeIndex, j, INF_CAPACITY ));
					pairEdgeIndex++;
				}

		FordFulkerson ff = new FordFulkerson(network, s, t);
		
		eliminated_[index] = false;
		for(FlowEdge e: network.adj(s)) {
			if(e.flow() < e.capacity()) {
				eliminated_[index] = true;
				
				certificates_[index] = new java.util.LinkedList<String>();
				for(int i = 0; i < nt_; i++)
					if(ff.inCut(i))
						certificates_[index].add(names_.get(i));
				
				break;
			}
		}
	}

	// number of teams
	public int numberOfTeams()
	{
		return nt_;
	}

	// all teams
	public Iterable<String> teams()
	{
		return names_;
	}
	
	private int teamIndex(String team)
	{
		int ind = 0;
		for(String t: names_)
			if(t.equals(team))
				return ind;
			else
				ind++;
		
		throw new java.lang.IllegalArgumentException();
	}

	// number of wins for given team
	public int wins(String team)
	{
		return w_[teamIndex(team)];
	}

	// number of losses for given team
	public int losses(String team)
	{
		return l_[teamIndex(team)];
	}

	// number of remaining games for given team
	public int remaining(String team)
	{
		return r_[teamIndex(team)];
	}

	// number of remaining games between team1 and team2
	public int against(String team1, String team2)
	{
		return g_[teamIndex(team1)][teamIndex(team2)];
	}

	// is given team eliminated?
	public boolean isEliminated(String team)
	{
		return eliminated_[teamIndex(team)];
	}

	public Iterable<String> certificateOfElimination(String team)
	{ // subset R of teams that eliminates given team; null if not eliminated
		return certificates_[teamIndex(team)];
	}

	public static void main(String[] args)
	{
	    BaseballElimination division = new BaseballElimination(args[0]);
		StdOut.println("nteams: " + division.numberOfTeams());
		
	    for (String team : division.teams()) {
	        if (division.isEliminated(team)) {
	            StdOut.print(team + " is eliminated by the subset R = { ");
	            for (String t : division.certificateOfElimination(team))
	                StdOut.print(t + " ");
	            StdOut.println("}");
	        }
	        else {
	            StdOut.println(team + " is not eliminated");
	        }
	    }
	    /*
		FlowNetwork network = new FlowNetwork(5);

		network.addEdge(new FlowEdge(1, 2, 0.5));

		int s = 0, t = 1;

		FordFulkerson ff = new FordFulkerson(network, s, t);

		ff.inCut(5);*/
	}
}
